/**
 * 接雨水
 *
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *
 * 示例 1：
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 *
 * 示例 2：
 * 输入：height = [4,2,0,3,2,5]
 * 输出：9
 *
 * 提示：
 * n == height.length
 * 1 <= n <= 2 * 104
 * 0 <= height[i] <= 105
 */

/**
 * 这题我也是取巧了, 这个水面起起伏伏的是真的不好写, 那我们就把他转化为平整的平面,
 * 我们加上黑色的区域组成一个平面, 然后再减去灰色的区域就是剩下的水的体积, 首先我们的
 * 灰色体积很容易来求, 所以我们的主要操作是来求整体的面积, 我们来从左向右观察, 我们发现
 * 只有后面的比前面的高, 我们就要求体积了, 但是当我们抵达最高的点, 后面的规律又不是这样的
 * 了, 我们试着来找规律, 发现并不是很好找, 但是转念一想, 我们从后向前看不就又是和前面
 * 一样的了吗
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {

    public static void main(String[] args) {
        Main test = new Main();
        test.trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1});
    }

    public int trap(int[] nums) {

        // 定义出总的体积 和 灰色体积
        int sum = 0, decSum = 0;

        // 数组长度
        int n = nums.length;

        // 求灰色体积
        for (int i : nums) {
            decSum += i;
        }

        // 这里我们要求出最大值, 因为最大值可能有很多, 但是两个最大值是可以直接
        // 填满的, 所以现在我们只要确定一下第一个出现的最大值和最后一个出现的最大
        // 值就可以了

        // 记录最大值
        int tmp = -1;

        // 分别记录第一个最大值和最后一个最大值
        int first = 0, last = 0;

        // 求第一个最大值
        for (int i = 0; i < n; i++) {
            if (tmp < nums[i]) {
                tmp = nums[i];
                first = i;
            }
        }

        // 求最后一个最大值
        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] == tmp) {
                last = i;
                break;
            }
        }

        // 先求最大值中间的体积
        sum += (last - first + 1) * tmp;

        // 后面两个求法还是有个小细节的, 我们不要将后面边界的体积也加进去
        // 所以直接是 right - left 就可以了

        // 求开头到第一个最大值的体积
        for (int left = 0, right = 0; right <= first; right++) {

            // 这里要是右边大于等于左边就要求一次体积, 并更新左边
            if (nums[right] >= nums[left]) {
                sum += (right - left) * nums[left];
                left = right;
            }
        }

        // 求结尾到最后一个最大值的体积
        for (int left = n - 1, right = n - 1; left >= last; left--) {

            // 这里要是左边大于等于右边就要求一次体积, 并更新右边
            if (nums[left] >= nums[right]) {
                sum += (right - left) * nums[right];
                right = left;
            }
        }

        return sum - decSum;
    }
}